#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
private:
    int maxDepth = INT32_MIN;
    int res;

    void traversal(TreeNode * node, int depth){
        if(node->left == nullptr && node->right == nullptr){
            if (maxDepth < depth){
                maxDepth = depth;
                res = node->val;
            }
            return;
        }
        if(node->left) traversal(node->left, depth + 1);
        if(node->right) traversal(node->right, depth + 1);
    }
public:
    int findBottomLeftValue(TreeNode* root) {
        // 1、递归法
        // traversal(root, 1);
        // return res;

        // 2、迭代法
        queue<TreeNode *> que;
        int res;
        if(root) que.push(root);
        while(!que.empty()){
            int size = que.size();
            for(int i=0; i<size; i++){
                TreeNode * node = que.front();
                que.pop();
                if(i == 0) res = node->val;
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return res;
    }
};